package com.azure.code.slidingwindow.queue;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 滑动窗口的最大值
 * 给你输入一个数组nums和一个正整数k，有一个大小为k的窗口在nums从左向右滑动，请你每次输出窗口中k个元素的最大值
 */
public class MaxSlidingWindow_239 {

    /**
     * 优先级队列解法
     */
    int[] maxSlidingWindow(int[] nums, int k){
        MonotonicQueue window = new MonotonicQueue();
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++){
            if(i<k-1){
                // 先把窗口前k-1填满
                window.push(nums[i]);
            }else {
                // 窗口开始向前滑动
                window.push(nums[i]);
                // 将当前窗口中最大元素记入结果
                res.add(window.max());
                // 移出最后的元素
                window.pop(nums[i-k+1]);
            }
        }
        int[] arr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
//        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    // 单调队列的实现
    static class MonotonicQueue{
        LinkedList<Integer> q = new LinkedList<>();
        // 在队尾添加元素n
        void push(int n){
            // 将小于n的元素全部删除
            while (!q.isEmpty()&&q.getLast()<n){
                q.pollLast();
            }
            q.addLast(n);
        }
        // 返回当前队列中最大的值
        int max(){
            return q.getFirst();
        }
        // 对头元素如果是n，删除它
        void pop(int n){
            if(n==q.getFirst()){
                q.pollFirst();
            }
        }
    }
}
